/****************************************************************************
 *
 *   Copyright (C) 2024 MicoAir Development Team. All rights reserved.
 *   Adapted from PX4 Autopilot Project (BSD-3-Clause License)
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 * 3. Neither the name PX4 nor the names of its contributors may be
 *    used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 ****************************************************************************/

/**
 * @file intrusive_sorted_list.h
 *
 * An intrusive linked list where nodes are sorted on insertion.
 * 
 * This is a C-language implementation of PX4's IntrusiveSortedList.
 * Nodes are sorted using a user-provided comparison function.
 * Zero memory allocation - nodes are embedded in the user's data structure.
 */

#pragma once

#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @brief Intrusive sorted list node
 * 
 * Embed this structure in your data structure to make it sortable.
 * Example:
 *   typedef struct {
 *       intrusive_sorted_list_node_t node;
 *       int priority;
 *       // ... other fields
 *   } my_item_t;
 */
typedef struct intrusive_sorted_list_node {
	struct intrusive_sorted_list_node *sibling;
} intrusive_sorted_list_node_t;

/**
 * @brief Comparison function type
 * 
 * @param a Pointer to first item (not the node!)
 * @param b Pointer to second item (not the node!)
 * @return true if a <= b (a should come before or equal to b)
 */
typedef bool (*intrusive_sorted_list_compare_fn)(const void *a, const void *b);

/**
 * @brief Intrusive sorted list
 */
typedef struct {
	intrusive_sorted_list_node_t *head;  ///< Head of the list
	size_t node_offset;                   ///< Offset of node in item structure
	intrusive_sorted_list_compare_fn compare; ///< Comparison function
} intrusive_sorted_list_t;

/**
 * @brief Initialize an intrusive sorted list
 * 
 * @param list Pointer to list structure
 * @param node_offset Offset of intrusive_sorted_list_node_t in your structure (use offsetof())
 * @param compare Comparison function
 */
void intrusive_sorted_list_init(intrusive_sorted_list_t *list, size_t node_offset,
                                 intrusive_sorted_list_compare_fn compare);

/**
 * @brief Add an item to the sorted list
 * 
 * The item is inserted in sorted order according to the comparison function.
 * 
 * @param list Pointer to list
 * @param item Pointer to item to add (not the node!)
 */
void intrusive_sorted_list_add(intrusive_sorted_list_t *list, void *item);

/**
 * @brief Remove an item from the list
 * 
 * @param list Pointer to list
 * @param item Pointer to item to remove (not the node!)
 * @return true if item was found and removed, false otherwise
 */
bool intrusive_sorted_list_remove(intrusive_sorted_list_t *list, void *item);

/**
 * @brief Get the head (first) item of the list
 * 
 * @param list Pointer to list
 * @return Pointer to first item, or NULL if list is empty
 */
void *intrusive_sorted_list_head(const intrusive_sorted_list_t *list);

/**
 * @brief Check if the list is empty
 * 
 * @param list Pointer to list
 * @return true if empty, false otherwise
 */
bool intrusive_sorted_list_empty(const intrusive_sorted_list_t *list);

/**
 * @brief Get the size of the list
 * 
 * @param list Pointer to list
 * @return Number of items in the list
 */
size_t intrusive_sorted_list_size(const intrusive_sorted_list_t *list);

/**
 * @brief Clear the list (does not free memory)
 * 
 * @param list Pointer to list
 */
void intrusive_sorted_list_clear(intrusive_sorted_list_t *list);

/**
 * @brief Get the next item in the list
 * 
 * @param list Pointer to list
 * @param item Current item
 * @return Next item, or NULL if at end
 */
void *intrusive_sorted_list_next(const intrusive_sorted_list_t *list, const void *item);

#ifdef __cplusplus
}
#endif

